class Solution {
public:

    const char * Strstr(const char *s, const char *p) {
      if (*s == 0) {
        return *p == 0 ? s : NULL;
      }
      int n = strlen(s);
      int m = strlen(p);
      if (n < m) {
        return NULL;
      }

      for (int i = 0; i + m <= n; ++i) {
        int j = 0;
        for (; j < m; ++j) {
          if (p[j] == '?' || s[i + j] == p[j]) {
            continue;
          }
          break;
        }
        if (j >= m) {
          return s + i;
        }
      }
      return NULL;
    }


    bool isMatch(const char *s, const char *p) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (s == NULL || p == NULL) {
          return false;
        }
        if (*p == 0) {
          return *s == 0;
        }
        vector<string> parts;
        int n = strlen(s);
        int m = strlen(p);

        for (int i = 0; i < m;) {
          string str;
          int j = i;

          for (; p[j] != '*' && p[j] != 0; ++j) {
            str += p[j];
          }
          parts.push_back(str);
          i = j + 1;
        }
        if (p[m - 1] == '*') {
          parts.push_back("");
        }

        if (parts.size() == 1) {
          return n == m && Strstr(s, p);
        }

        int cur = 0;
        for (int i = 0; i < parts.size(); ++i) {
          const char* pos = NULL;
          if (i == 0) {
            if (Strstr(s + cur, parts[i].c_str()) != s) {
              return false;
            }
            cur += parts[i].length();
          } else if (i == parts.size() - 1) {
            if (!(n - cur >= parts[i].length() &&
                 Strstr(s + (n - parts[i].length()), parts[i].c_str()))) {
              return false;
            }
          } else {
            pos = Strstr(s + cur, parts[i].c_str());
            if (pos == NULL) {
              return false;
            }
            cur = pos - s + parts[i].length();
          }
        }
        return true;
      }
};
